//快速排序
public class QuickSort
{
    public static void main(String[] args)
    {
        int[] arr = getRandomArray(20);
        for (int i : arr)
        {
            System.out.print(i + " ");
        }
        System.out.println();
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr)
        {
            System.out.print(i + " ");
        }
    }

    public static void quickSort(int[] arr, int left, int right)
    {
        if (left >= right)
        {
            return;
        }
        //设置最左边的元素为基准值
        int key = arr[left];
        //数组中比key小的放在左边，比key大的放在右边，key值下标为i
        int i = left;
        int j = right;
        while (i < j)
        {
            //j向左移，直到遇到比key小的值
            while (arr[j] >= key && i < j)
            {
                j--;
            }
            //i向右移，直到遇到比key大的值
            while (arr[i] <= key && i < j)
            {
                i++;
            }
            //i和j指向的元素交换
            if (i < j) swap(arr, i, j);
        }

        arr[left] = arr[i];
        arr[i] = key;

        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);

    }


    private static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int[] getRandomArray(int n)
    {
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++)
        {
            arr[i] = (int) (Math.random() * n + 1);
        }
        return arr;
    }
}
